home *** CD-ROM | disk | FTP | other *** search
/ Fritz: All Fritz / All Fritz.zip / All Fritz / FILES / PROGNG_C / TURBOCU1.LZH / HSORT.C < prev    next >
Text File  |  1987-09-05  |  8KB  |  302 lines
  1. /***********************************************************************/
  2. /*  HSORT(): Heap Sort function.                                       */
  3. /*  See the function declaration for calling information.              */
  4. /*  Set STANDALONE != 0 to compile a shell to test the sucker;         */
  5. /*    to compile just hsort() and its supporting functions, set        */
  6. /*    STANDALONE = 0.                                                  */
  7. /* DEBUG determines how much debugging info is displayed; 0 is none.   */
  8. /* TRACE determines what level of tracing information is displayed;    */
  9. /*    0 is none.                                                       */
  10. /* Function is by Bruce Feist; please contact me on CompuServe with    */
  11. /*    a message on BORPRO or through EASYPLEX if you have any          */
  12. /*    questions or problems.                                           */
  13. /* Feel free to make use of this code in your own programs.            */
  14. /***********************************************************************/
  15.  
  16. #define DEBUG 0
  17. #define STANDALONE 0
  18. #define TRACE 0
  19.  
  20. #include <stdio.h>
  21. #include <process.h>
  22. #include <alloc.h>
  23. #include <stdlib.h>
  24. #include <mem.h>
  25.  
  26. static void pascal swap (unsigned int, unsigned int);
  27. static void pascal buildheap (void);
  28. static void pascal heapify (unsigned int, unsigned int);
  29. void       hsort (void *, unsigned int, unsigned int, int (*)());
  30.  
  31. #if STANDALONE
  32. static int int_compare (int *, int *);
  33. static void showarray (int *, unsigned int, unsigned int);
  34.  
  35. void
  36. main()
  37. {
  38.   unsigned int n_entries, entry_num;
  39.   int *entries;
  40.  
  41.   printf ("How many entries do you wish to sort?  ");
  42.   scanf ("%d", &n_entries);
  43.   entries = (int *) malloc (n_entries * sizeof(int));
  44.  
  45.   for (entry_num = 0; entry_num < n_entries; entry_num++)
  46.   {
  47.     printf ("Enter #%d:  ", entry_num);
  48.     scanf ("%d", entries + entry_num);
  49.     }
  50.  
  51.   printf ("\n");
  52.  
  53.   hsort (entries, n_entries, sizeof (int), int_compare);
  54.  
  55.   showarray (entries, 0, n_entries - 1);
  56.  
  57.   exit (0);
  58.   }
  59.  
  60.  
  61. int
  62. int_compare (i, j)
  63. int *i, *j;
  64. {
  65.   return (*i - *j);
  66.   }
  67.  
  68.  
  69. void
  70. showarray(base, bot, top)
  71. int *base;
  72. unsigned int bot, top;
  73. {
  74.   unsigned int i;
  75.  
  76.   for (i=bot; i<=top; i++)
  77.     printf("%4d", base[i]);
  78.   printf ("\n");
  79.   }
  80.  
  81. #endif   /* STANDALONE */
  82.  
  83.  
  84. static int (*static_compare) (void *, void *), static_width, static_n_elements;
  85. static void *temp_element, *static_base;
  86.  
  87. void
  88. hsort(base, n_elements, element_width, compare)
  89. /***************************************************************************/
  90. /* Heap Sort routine -- similar in calling sequence to standard 'qsort()'  */
  91. /* Base is a pointer to an array                                           */
  92. /* n_elements is the number of elements in the array                       */
  93. /* element_width is the width of each element in bytes                     */
  94. /* compare is a function of two pointers (each to an element of the array) */
  95. /*    returning a negative value if the first is smaller, a positive value */
  96. /*    if the second is smaller, or 0 if they should be sorted the same.    */
  97. /* Warning!  This function will halt your program if it can't allocate     */
  98. /*    element_width bytes using malloc().                                  */
  99. /***************************************************************************/
  100.  
  101. void *base;
  102. unsigned int  n_elements, element_width;
  103. int           (*compare)();
  104. {
  105.   register unsigned int i;
  106.  
  107. #if TRACE >= 1
  108.   printf("hsort(base at %lX, %u elements, width %u, compare at %ld)\n",
  109.          (long) base, n_elements, element_width, (long) compare);
  110. #endif
  111.  
  112.   /* this lets us reference elements of array as 1 to n */
  113.  
  114.   (char *) base -= element_width;
  115.  
  116.   /*  The following assignments to static variables reduce the */
  117.   /* overhead of subroutine calls later.                       */
  118.  
  119.   static_width = element_width;
  120.   static_compare = compare;
  121.   static_n_elements = n_elements;
  122.   static_base = base;
  123.  
  124.   temp_element = malloc (element_width);
  125.  
  126.   if (temp_element == NULL)
  127.   {
  128.     fputs ("Unable to allocate room for a temporary element in hsort().\n",
  129.            stderr);
  130.     exit (1);
  131.     }
  132.  
  133.  
  134.   buildheap ();
  135.  
  136.   for (i = n_elements; i>1; i--)
  137.   {
  138.     swap (1, i);
  139.     heapify (1, i-1);
  140.     }
  141.  
  142.   free (temp_element);
  143.   }
  144.  
  145.  
  146. static void pascal
  147. swap (i, j)
  148. unsigned int i,j;
  149.  
  150. {
  151.   register int temp_int;
  152.   long temp_long;
  153.  
  154. #if TRACE >= 2
  155.   printf("swap (i=%d, j=%d) called.\n",i,j);
  156. #endif
  157.  
  158.   switch (static_width)
  159.   {
  160.     case sizeof (int): temp_int = ((int *) static_base) [i];
  161.                        ((int *) static_base) [i] = ((int *) static_base) [j];
  162.                        ((int *) static_base) [j] = temp_int;
  163.                        break;
  164.  
  165.     case sizeof(long): temp_long = ((long *) static_base) [i];
  166.                        ((long *) static_base) [i] = ((long *) static_base) [j];
  167.                        ((long *) static_base) [j] = temp_long;
  168.                        break;
  169.  
  170.     case sizeof(char): temp_int = ((char *) static_base) [i];
  171.                        ((char *) static_base) [i] = ((char *) static_base) [j];
  172.                        ((char *) static_base) [j] = (char) temp_int;
  173.                        break;
  174.  
  175.     default:           memcpy (temp_element,
  176.                                (char *) static_base + i*static_width,
  177.                                static_width);
  178.                       memcpy ((char *) static_base + i*static_width,
  179.                               (char *) static_base + j*static_width,
  180.                               static_width);
  181.                       memcpy ((char *) static_base + j*static_width,
  182.                               temp_element,
  183.                               static_width);
  184.                       break;
  185.     }  /* end of switch */
  186.  
  187. #if TRACE >= 2
  188.   printf ("swap exited.\n");
  189. #endif
  190.   }
  191.  
  192.  
  193. static void pascal
  194. buildheap()
  195.  
  196. {
  197.   register unsigned int element_number;
  198.  
  199. #if TRACE >= 2
  200.   printf("buildheap() called.\n");
  201. #endif
  202.  
  203.   for (element_number = static_n_elements >> 1;
  204.        element_number >= 1;
  205.        element_number--)
  206.   {
  207. #if DEBUG >= 2
  208.     printf ("buildheap calls heapify (%d, %d).\n",
  209.             element_number, static_n_elements);
  210. #endif
  211.     heapify(element_number, static_n_elements);
  212.     }
  213.  
  214. #if TRACE >= 2
  215.   printf ("buildheap exited.\n");
  216. #endif
  217.   }
  218.  
  219.  
  220. #define son1(i)    (i << 1)
  221. #define son2(i)    ((i << 1) + 1)
  222. #define pointer(i) ((char *) static_base + i * static_width)
  223. #define child_count(i, j) \
  224.      (j > son1(i) \
  225.        ? 2 \
  226.        : j < son1(i) \
  227.           ? 0 \
  228.           : 1)
  229.  
  230.  
  231. static void pascal
  232. heapify (i,j)
  233.  
  234. unsigned int i, j;
  235. {
  236.   /* The following are static to avoid recursive stack overhead */
  237.  
  238.   static unsigned int son1i, son2i;
  239.   static void *pson1, *pson2, *pi;
  240.   static unsigned int k;
  241.  
  242. #if TRACE >= 3
  243.   printf("heapify(i=%d, j=%d) called.\n", i, j);
  244. #endif
  245.  
  246.   son1i = son1 (i);
  247.   son2i = son2 (i);
  248.   pson1 = pointer (son1i);
  249.   pson2 = pointer (son2i);
  250.   pi    = pointer (i);
  251.  
  252. #if DEBUG >= 2
  253.   printf ("child_count (%d) = %d.\n", i, child_count(i, j));
  254. #endif
  255.  
  256.   switch (child_count (i, j))
  257.   {
  258.     case 0: break;
  259.  
  260.     case 2: {
  261.               k = (*static_compare) (pson1, pson2) > 0 ? son1i : son2i;
  262.               if ((*static_compare) (pi, pointer (k)) < 0)
  263.               {
  264. #if STANDALONE && DEBUG >= 1
  265.                 printf ("heapify changes\n");
  266.                 showarray (static_base, 1, static_n_elements);
  267. #endif
  268.  
  269.                 swap (i, k);
  270.                 heapify (k, j);
  271.  
  272. #if STANDALONE && DEBUG >= 1
  273.                 printf ("into\n");
  274.                 showarray (static_base, 1, static_n_elements);
  275. #endif
  276.                 }
  277.               break;
  278.             }  /* end case */
  279.  
  280.     case 1: if ((*static_compare) (pi, pson1) < 0)
  281.             {
  282. #if STANDALONE && DEBUG >= 1
  283.               printf ("heapify changes\n");
  284.               showarray (static_base, 1, static_n_elements);
  285. #endif
  286.  
  287.               swap (i, son1i);
  288.               heapify (son1i, j);
  289.  
  290. #if STANDALONE && DEBUG >= 1
  291.               printf ("into\n");
  292.               showarray (static_base, 1, static_n_elements);
  293. #endif
  294.               }
  295.             break;
  296.     }  /* end of case */
  297.  
  298. #if TRACE >= 3
  299.   printf ("heapify exited.\n");
  300. #endif
  301.   }
  302.